using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;

namespace Ants {

	public class AntsBot : Bot {

        /// <summary>
        /// Initializes a isntance of <see cref="AntsBot"/> class
        /// </summary>
        public AntsBot() {            
            Orders = new Dictionary<Location, Ant>();
            AntOrders = new Dictionary<Ant, Location>();
        }

        /// <summary>
        /// Collection of orders for ants
        /// </summary>
        private IDictionary<Location, Ant> Orders { get; set; }

        private IDictionary<Ant, Location> AntOrders { get; set; }

		// DoTurn is run once per turn
		public override void DoTurn (IGameState state) {
		    Program.Log("DoTurn");
            Program.Log(DateTime.Now.ToString());		    
            try {
                // reset orders
                Orders = new Dictionary<Location, Ant>();
                // loop through all my ants and try to give them orders);
                foreach (Ant ant in state.MyAnts) {
                    Program.Log("ant=" + ant);
                    // check if ant has already assigned order););)
                    if (AntOrders.Any(x => x.Key.Equals(ant))) {
                        Program.Log("antOrdered");
                        var goal = AntOrders[ant];
                        if (ant.Equals(goal)) {
                            Program.Log("goal reached");
                            // order finished
                            AntOrders.Remove(ant);
                        }
                        else {
                            Program.Log("calc path");
                            Program.Log("remaining=" + state.TimeRemaining);
                            // calculate path
                            var path = FindShortestPath(state, ant, goal);
                            Program.Log("calc path done");
                            Program.Log("remaining=" + state.TimeRemaining);
                            if (path.Count > 0) {
                                IssueOrder(state, ant, path.Peek());

                                AntOrders.Remove(ant);
                                AntOrders.Add(new Ant(path.Peek(), ant.Team), goal);
                            }
                            continue;
                        }
                    }
                    foreach (var foodTile in state.FoodTiles.OrderBy(x => state.GetDistance(ant, x))) {                        
                        if (AntOrders.Any(x => x.Value.Equals(foodTile))) {
                            continue;
                        }
                        if (state.GetDistance(ant, foodTile) > 20) {
                            continue;
                        }
                        Program.Log("calc path 2");
                        Program.Log("remaining=" + state.TimeRemaining);
                        // find shortes path to food
                        var path = FindShortestPath(state, ant, foodTile);
                        Program.Log("calc path done 2");
                        Program.Log("remaining=" + state.TimeRemaining);
                        if (path.Count > 0) {                            
                            IssueOrder(state, ant, path.Peek());
                            // mark food as orders                            
                            AntOrders.Add(new Ant(path.Peek().Row, path.Peek().Col, ant.Team), foodTile);
                           
                            break;
                        }
                    }
                    
                    // check if we have time left to calculate more orders
                    if (state.TimeRemaining < 10) break;
                }
            }catch(Exception ex) {
                Program.Log(ex.ToString());
            }
            Program.Log("remaining=" + state.TimeRemaining);
		}

        protected void IssueOrder(IGameState state, Ant ant, Location destinationLocation)
        {            
            base.IssueOrder(ant, state.GetDirections(ant, destinationLocation).First());
            Orders.Add(destinationLocation, ant);
        }

        protected void IssueOrder(IGameState state, Ant ant, Direction direction)
        {
            base.IssueOrder(ant, direction);
            Orders.Add(state.GetDestination(ant, direction), ant);
        }

        /// <summary>
        /// Gets the stortes path from ant to goal
        /// </summary>
        /// <param name="state"></param>
        /// <param name="ant"></param>
        /// <param name="goal"></param>
        /// <returns></returns>
        public Stack<Location> FindShortestPath(IGameState state, Location ant, Location goal) {            
            var closedSet = new List<Location>();                        
            Program.Log("FindShortestPath(ant=" + ant + "; goal=" + goal);
            var g = new Dictionary<Location, int>();
            var h = new Dictionary<Location, int>();
            var f = new Dictionary<Location, int>();
            var parents = new Dictionary<Location, Location>();

            var path = new Stack<Location>();

            if (state.GetIsPassable(goal) &&
                state.GetIsUnoccupied(goal) &&
                !Orders.Any(x => x.Key.Equals(goal))) {

                g[ant] = 0;
                h[ant] = state.GetDistance(ant, goal);
                f[ant] = g[ant] + h[ant];

                var openSet = new List<Location>();
                openSet.Add(ant);

                while (openSet.Count > 0) {
                    Location currentLocation = openSet[0];
                    if (currentLocation.Equals(goal)) {
                        var parent = goal;
                        while (parent != null) {
                            if (!parent.Equals(ant)) {
                                path.Push(parent);
                            }
                            parent = parents.ContainsKey(parent) ? parents[parent] : null;
                        }
                        return path;
                    }
                    openSet.RemoveAt(0);
                    closedSet.Add(currentLocation);
                    var neighborLocations = new[]
                                                {
                                                    state.GetDestination(currentLocation, Direction.North),
                                                    state.GetDestination(currentLocation, Direction.South),
                                                    state.GetDestination(currentLocation, Direction.West),
                                                    state.GetDestination(currentLocation, Direction.East)
                                                };
                    foreach (var neighborLocation in neighborLocations) {
                        if (closedSet.Contains(neighborLocation) ||
                            !state.GetIsPassable(neighborLocation) ||
                            !state.GetIsUnoccupied(neighborLocation) ||
                            Orders.Any(x => x.Key.Equals(neighborLocation)))
                            continue;
                        var tentativeG = g[currentLocation] + state.GetDistance(currentLocation, neighborLocation);
                        bool neighborLocationIsInOpenSet = openSet.Contains(neighborLocation);
                        if (!neighborLocationIsInOpenSet || tentativeG < g[neighborLocation]) {
                            parents[neighborLocation] = currentLocation;
                            var gn = g[neighborLocation] = tentativeG;
                            var hn = h[neighborLocation] = state.GetDistance(neighborLocation, goal);
                            var fn = f[neighborLocation] = gn + hn;
                            if (!neighborLocationIsInOpenSet) {
                                var insertIndex = openSet.Count;
                                for (int i = 0; i < openSet.Count; i++) {
                                    if (f[openSet[i]] > fn) {
                                        insertIndex = i;
                                        break;
                                    }
                                }
                                openSet.Insert(insertIndex, neighborLocation);
                            }
                        }
                    }
                }
            }
            return path;
        }        
	}        
}